'''
https://leetcode.cn/problems/first-missing-positive/
'''

from typing import List


class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        l, r = 0, len(nums)
        while l < r:
            if nums[l] == l + 1:
                # good, 往下走
                l += 1
            elif nums[l] <= l or nums[l] > r or nums[l] == nums[nums[l] - 1]:
                # nums[l] <= l：表示了如果这个数 < 1，
                #                   或者走到后边了，又遇到一个较小的数
                #                   其实这个情况其实也会被nums[l] == nums[nums[l] - 1]这个判断给覆盖到
                # nums[l] > r： 这个数是不可望也不可得的
                # nums[l] == nums[nums[l] - 1]：这个数在已经在他的位置上了，所以现在这个数重复的可以丢弃了
                #                    这个数有可能在前边出现过，但是会被nums[l] <= l给cover到
                #                    也有可能在后边出现
                r -= 1
                nums[l], nums[r] = nums[r], nums[l]
            else:
                # nums[l] ！= nums[nums[l] - 1]： 他把换到那个位置上
                nums[nums[l] - 1], nums[l] = nums[l], nums[nums[l] - 1]
        return l + 1
